前言

昨天實作 SARSA 演算法，今天要實作 off-policy 的 TD Learning 方法：Q-Learning。由於內容大致上相同，因此今天會著重在與 SARSA 不同之處。

實作 Q-Learning

今天要實作的 Q-Learning，一樣分為五個函數處理，分別為

• 模擬環境中運行 (SimProc)
• 決定動作 (GetAction)
• 更新價值函數 (ValueUpdate)
• 顯示目前最佳策略 (PrintGreedyPolicy)
• 主程式 (main)

其中只有 SimProc 與 ValueUpdata 的部分與 SARSA 不同，因此以下針對這兩個函數進行說明。一樣可以在 GitHub 查看完整內容。

SimProc

def SimProc(action_value, reward, trans_mat, steps, gamma, alpha, epsilon):
    # initialize setting
    record = []
    state = np.random.randint(1,15)
    for step in range(steps):
        # get next infromation
        action = GetAction(action_value, epsilon, state)
        next_state = np.argmax(trans_mat[:,state,action])
        record.append([state, action, reward[next_state], next_state])
        # update action value
        action_value[state, action] = ValueUpdate(action_value, record[step], alpha, gamma)
        # update for next step
        state = next_state
        if state == 0 or state == 15:
            break
    return action_value

與 SARSA 方法不同之處主要在於

• 每個 step 中，只需要決定現在的 action：
  在 SARSA 中需要 next_action 來更新動作價值，然而在 Q-Learning 中不需要，因此每個 step 中只需決定現在的 action。

因此我們在實作上，沒有 next_action 這個變數，在 record 中也不需記錄這個參數。

ValueUpdate

def ValueUpdate(action_value, record, alpha, gamma):
    state = record[0]
    action = record[1]
    reward = record[2]
    next_state = record[3]
    now_value = action_value[state, action]
    update_value = alpha*(reward + gamma*np.max(action_value[next_state,:]) - now_value)
    value = now_value + update_value
    return value

與 SARSA 方法不同之處主要在於

• 永遠使用貪婪法更新動作狀態：
  在 Q-Learning 中，未來的動作作態由「下一步的動作狀態最大值」決定，相較於 SARSA 差異在於探索時，SARSA會使用探索的動作價值更新，而 Q-Learning 不是。

因此在實作上，主要的差異在於 update_value 這個變數，我們改採用 action_value 的最大值估計下一狀態的動作價值。

執行結果

============================================================
[Greedy Policy]
Episode: 1000
[['*' '<' '<' '<']
 ['^' '^' 'v' 'v']
 ['^' '^' '>' 'v']
 ['>' '>' '>' '*']]
============================================================

看起來的結果與 SARSA 有差異，但我們不能保證是不是模擬過程造成的差異。

SARSA 與 Q-Learning

從 GridWorld 的例子中，我們看不太出這兩個演算法的差別。從數學上來看，可以推測 Q-Learning 產出的動作價值會高於 SARSA，畢竟 Q-Learning 每一次都使用最大價值更新，不過在 GridWorld 中並沒有發現特別的差異：

[SARSA - max action value]
[[ 0.          0.         -0.99919909 -1.79209217]
 [ 0.         -0.93548848 -1.42440894 -0.99739422]
 [-0.99711271 -1.40733501 -0.94895313  0.        ]
 [-1.74605935 -0.99796185  0.          0.        ]]

[Q-Learning - max action value]
[[ 0.          0.         -0.99680078 -1.73150158]
 [ 0.         -0.95623369 -1.52771181 -0.99645516]
 [-0.99835771 -1.44740146 -0.95842201  0.        ]
 [-1.68129873 -0.99827127  0.          0.        ]]

這是 Day 24 與 Day 25 的策略下，對應的動作價值。

在書上提了一個稱為 cliff-walking 的例子，說明了 SARSA 是一個比較保守的方法。明天將會介紹這個例子、應用 SARSA 與 Q-Learning 於該問題、並比較兩者的結果。